Next generation networks are expected to provide increasingly sophisticated services beyond simple connectivity such as security, quality of service (QoS), load balancing, and traffic accounting. A fundamental requirement in providing this value-added services is the ability to classify packets.
The difficulty of packet classification is determined by three factors: (1) the complexity of the filters; (2) the number of filters; and (3) the rate of packet arrivals. The first and second factors bound the amount of work required for a single packet, while the third factor gives the aggregate amount of work per unit time.
Regarding the first factor, filters for IP networks are typically based on the TCP/UDP/IP headers, and their constructions are fairly standardized. See, for instance, document no. 6 in the list of references detailed below (prior to the summary of invention). All of the listed references are incorporated by reference herein in their entirety.
Regarding the second factor, existing filter tables tend to be small (×10s to ×100s of filters) as performance degrades severely with large filter tables. However, for fine-grained policy control, the number of filters should ideally be large, ranging upward to ×100 Ks.
Regarding the third factor, the packet arrival rate is in turn determined by the input link speed and the packet size. The former is increasing at an unprecedented rate (e.g., Gigabit Ethernet in LAN, and OC-48 in WAN backbones), while the latter is decreasing to an average of 200 bytes as reported in reference document nos. 7 and 11. This combination has exacerbated the problem. For example, the worst-case packet arrival rate of an OC-12 link (assuming 64-byte packet size, 5% SONET overhead and use of Packet Over SONET protocol) is around 1 million packets per second.
The problem of packet classification can be cast as an abstract mathematical problem. For example, the problem is similar in nature to the problem of range matching in computational geometry. See reference document no. 4. There are various known algorithms that can be adapted, and theoretical results are also known. In the context of IP packets, the problems have been studied in reference document nos. 5, 9 and 10.
Most of these studies, however, focus on worst-case performance, and do not take into account actual filter usage statistics, nor the types of commonly occurring filter patterns. Moreover, they provide sparse experimental results. In particular, the asymptotic complexity does not accurately tell how the algorithms scale to large number (e.g., from 4K to 1M) of filters.
A more pragmatic approach is desired. In particular, it is desireable to be able to classify packets using a relatively large number of filters given the present state of packet arrival rates. Towards this end the invention seeks to provide a relatively efficient method and system for finding or identifying an applicable filter when a relatively large number of filters are employed in a packet clasification system.